package algorithm.string;

import java.util.Arrays;

/**
 * KMP算法（字符串匹配的加速算法）
 * 每次失配，S串的索引i不动，P串的索引J定位到某个数
 * 提升时间效率，相对于BruteForceMath
 * 参考：https://www.cnblogs.com/dusf/p/kmp.html
 */
public class KmpMath {
    public static void main(String[] args) {
        char[] s = {'a','b','c','d','e','f','g','a','f','g','a','b','c'};
        char[] p = {'f','g','a','f','g','a'};
        //indexOfKMP(s,p);
        String ts = "abcabcabcde";
        String ps = "abcabcd";
        System.out.println(NaiveStringSearch(ts,ps));
        System.out.println(KMP(ts,ps));
    }

    /**
     * 朴素算法，即暴力匹配
     * @param s 主串
     * @param p 匹配串
     * @return
     */
    public static int NaiveStringSearch(String s, String p) {
        int i = 0;
        int j = 0;
        int s_len = s.length();
        int p_len = p.length();
        while(i<s_len && j< p_len){
            if(s.getBytes()[i] == p.getBytes()[j]){
                i++;
                j++;
            }
            else{
                i = i-j+1;
                j = 0;
            }
        }

        if(j==p_len){
            return i - j;
        }
        return -1;
    }

    /**
     * next算法
     * 实际上就是P往后移多少位
     * 1.因为在P的每一个位置都可能发生不匹配，也就是说要计算每一个位置的J对应的K，所以需要数组来保存
     * 2.因为下标从0开始的，K值实际是J位前的子串的最大重复子串的长度
     * @param ch 数组
     * @param clen 数组长度
     * @param next next数组
     * @return int
     */
    public static int getNext(char ch[],int clen,int next[]){
        next[1] = 0;
        int i=1,j=0;
        while(i<=clen){
            if (j == 0 || ch[i] == ch[j])
                next[++i] = ++j;
            else
                j = next[j];

        }
        return j;
    }

    /**
     * 拓展思路
     * ++i,i++
     * i++先做别的事，再给自己加1，++i先给自己加1，再做别的事
     * 独立使用时++i 和 i++二者效果一样
     * 表达式参与运算
     * ++i比i++效率要高些
     * 举例 a = ++i，相当于 i=i+1; a = i; a = i++，相当于 a = i; i=i+1
     *         int i = 1;
     *         int j = i++;
     *         System.out.println(j);
     *         System.out.println(i+" "+j);
     */
    public static int[] getNext(String ps) {
        char[] p = ps.toCharArray();
        int[] next = new int[p.length];
        //j已经在最左边了，不可能再移动了，这时候要应该是i指针后移。所以在代码中才会有next[0] = -1
        next[0] = -1;
        System.out.println("ps:"+ps);
        int j = 0;
        int k = -1;
        while(j < p.length -1) {
            if (k == -1)
                System.out.println(">"+p[j]);
            else
                System.out.println(">"+p[j]+"|"+p[k]);
            if (k==-1 || p[j] == p[k]) {
                next[++j] = ++k;
            } else {
                k = next[k];
            }
            System.out.println(">next:"+Arrays.toString(next));
        }
        return next;
    }

    public static int KMP(String ts, String ps) {
        //主串
        char[] t = ts.toCharArray();
        //匹配模式
        char[] p = ps.toCharArray();
        int i = 0;
        int j = 0;
        int[] next = getNext(ps);
        System.out.println("next:"+ Arrays.toString(next));
        while (i<t.length && j <p.length) {
            if (j == -1 || t[i] == p[j] ) {
                i++;
                j++;
            } else {
                j = next[j];// j回到指定位置
            }
        }
        if ( j == p.length ) {//成功
            return i-j;
        } else {//失败
            return -1;
        }
    }
}
